/**********************************************************

@description:
*File Name:B-tree.c
*Author: ydx
*mail: yudongxiang93@163.com
*Create Time: Fri 09 May 2025 07:57:26 AM CST
**********************************************************/
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include<string.h>
/**
 *1.key words array, key words length
 *2.child array, children length
 *3.parent
 *4.the order of the tree
 ***/
typedef struct bnode{
	int level;//jieshu
	int key_num,child_num;
	int *keys;
	struct bnode** children;
	struct bnode* parent;
}bnode;

bnode* init_bnode(int level){
	bnode* n=(bnode*)malloc(sizeof(bnode));
	n->level=level;
	n->key_num=0;
	n->child_num=0;
	n->keys=(int*)malloc((level+1)*sizeof(int));
	memset(n->keys,0,(level+1)*sizeof(int));
	n->children=(bnode**)malloc(sizeof(bnode*)*level);
	memset(n->children,0x0,level*sizeof(bnode*));
	n->parent=NULL;
	return n;
}
int findSuiteIndex(bnode* n,int data){
	int index;
	for(index=1;index<=n->key_num;index++){
		if(data<n->keys[index]){
			break;
		}
	}
	return index;
}
bnode* findSuiteLeafNode(bnode *t,int data){
	if(t->child_num==0){
		return t;
	}
	int index=findSuiteIndex(t,data);
	return findSuiteLeafNode(t->children[index-1],data);
}

void add_data(bnode* n,int data,bnode** t){
	int index=findSuiteIndex(n,data);
	for(int i=n->key_num;i>=index;i--){
		n->keys[i+1]=n->keys[i];
	}
	n->keys[index]=data;
	n->key_num++;
	//discuss if need to split
	if(n->key_num==n->level){
		//find the position to split
		int mid=n->level/2+n->level%2;//the index of keys
		bnode* lchild=init_bnode(n->level);
		bnode* rchild=init_bnode(n->level);
		for(int i=1;i<mid;i++){
			add_data(lchild,n->keys[i],t);
		}
		for(int i=mid+1;i<=n->key_num;i++){
			add_data(rchild,n->keys[i],t);
		}
		for(int i=0;i<mid;i++){
			lchild->children[i]=n->children[i];
			if(n->children[i]){
				n->children[i]->parent=lchild;
				lchild->child_num++;
			}
		}
		int idx=0;
		for(int i=mid;i<n->child_num;i++){
			rchild->children[idx++]=n->children[i];
			rchild->child_num++;
		}
		if(!n->parent){
			bnode* new_parent=init_bnode(n->level);
			add_data(new_parent,n->keys[mid],t);
			new_parent->children[0]=lchild;
			new_parent->children[1]=rchild;
			new_parent->child_num=2;
			lchild->parent=new_parent;
			rchild->parent=new_parent;
			*t=new_parent;
		}else{
			int idx1=findSuiteIndex(n->parent,n->keys[mid]);
			lchild->parent=n->parent;
			rchild->parent=n->parent;
			n->parent->children[idx1-1]=lchild;
			if(n->parent->children[idx1]){
				for(int i=n->parent->child_num-1;i>=idx1;i--){
					n->parent->children[i+1]=n->parent->children[i];
				}
			}
			n->parent->children[idx1]=rchild;
			n->parent->child_num++;
			add_data(n->parent,n->keys[mid],t);
		}
	}

}
void insert(bnode** t,int data){
	bnode* node=findSuiteLeafNode(*t,data);
	add_data(node,data,t);
}

int search(bnode* t,int data){
	if(!t)
		return -1;
	int index;
	for(index=1;index<=t->key_num;index++){
		if(data<t->keys[index])
			return search(t->children[index-1],data);
		else if(data==t->keys[index])
			return t->keys[index];
		else if(index==t->key_num || (index<t->key_num && data<t->keys[index+1]))
			return search(t->children[index],data);
		else 
			continue;
			
	}
}

void print_tree(bnode* t){
	if(t){
		for(int i=1;i<=t->key_num;i++){
			printf("%4d",t->keys[i]);
		}
		printf("\n");
	}
	for(int i=0;i<t->child_num;i++){
		print_tree(t->children[i]);
	}
}

int main(){
	bnode *t=init_bnode(5);
	insert(&t,1);
	insert(&t,2);
	insert(&t,3);
	insert(&t,4);
	insert(&t,5);
	insert(&t,6);
	insert(&t,7);
	insert(&t,8);
	insert(&t,9);
	insert(&t,10);
	insert(&t,11);
	insert(&t,12);
	insert(&t,13);
	insert(&t,14);
	insert(&t,16);
	insert(&t,17);
	insert(&t,18);
	print_tree(t);
	if(t->children[4]==NULL){
		printf("hello world\n");
	}
	printf("search:7:%d\n",search(t,7));
	printf("search:5:%d\n",search(t,5));
	printf("search:9:%d\n",search(t,9));
	printf("search:3:%d\n",search(t,3));
	printf("search:13:%d\n",search(t,13));
	printf("search:15:%d\n",search(t,15));
	printf("search:20:%d\n",search(t,20));
}
